package leetcode.daily;

import java.util.Arrays;

public class a_20201222 {

    public static int hammingWeight(int n) {
        int result = 0;
        int mask = 1;
        for(int i = 0; i < 32; i++){
            if((mask&n) != 0) result++;
            mask <<= 1;
        }
        return result;
    }

    public int maxSideLength(int[][] mat, int threshold) {
        if(mat == null || mat.length == 0) return 0;
        int m = mat.length;
        int n = mat[0].length;
        int[][][]dp = new int[m][n][2]; // dp[0] 保存右下角元素对应的正方形最大边长 dp[1]保存和
        int result = 0;
        // 初始化两条边
        for(int i = 0; i < m; i++){
            if(mat[i][0] <= threshold) {
                dp[i][0][0] = 1;
                dp[i][0][1] = mat[i][0];
                result = 1;
                if(result >= m || result >= n) return Math.min(m,n);
            }
        }
        for (int j = 0; j < n; j++){
            if(mat[0][j] <= threshold){
                dp[0][j][0] = 1;
                dp[0][j][1] = mat[0][j];
                result = 1;
                if(result >= m || result >= n) return Math.min(m,n);
            }
        }
        for(int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                int len = dp[i-1][j-1][0]+1;
                int sum = dp[i-1][j-1][1];
                do {
                    if(len == dp[i-1][j-1][0]+1){
                        sum = dp[i-1][j-1][1];
                        for(int z = 0; z < len; z++){
                            sum += mat[i][j-z];
                        }
                        for(int z = 1; z < len; z++){
                            sum += mat[i-z][j];
                        }
                        if(sum <= threshold) break;
                    }
                    else {
                        sum = getSum(mat, i, j, len);
                        if(sum <= threshold) break;
                    }
                }while (--len > 0);
                dp[i][j][0] = len;
                dp[i][j][1] = sum;
                result = Math.max(result, len);
                if(result >= m || result >= n) return Math.min(m,n);
            }
        }
        return result;
    }

    private static int getSum(int[][] mat, int m, int n, int len){
        int sum = 0;
        for(int i = 0; i < len; i++){
            for(int j = 0; j < len; j++){
                sum += mat[m-i][n-j];
            }
        }
        return sum;
    }

    /**
     * 1637. 两点之间不包含任何点的最宽垂直面积
     * 给你 n 个二维平面上的点 points ，其中 points[i] = [xi, yi] ，请你返回两点之间内部不包含任何点的 最宽垂直面积 的宽度。
     *
     * 垂直面积 的定义是固定宽度，而 y 轴上无限延伸的一块区域（也就是高度为无穷大）。 最宽垂直面积 为宽度最大的一个垂直面积。
     *
     * 请注意，垂直区域 边上 的点 不在 区域内。
     *
     *
     *
     * 示例 1：
     *
     * ​
     * 输入：points = [[8,7],[9,9],[7,4],[9,7]]
     * 输出：1
     * 解释：红色区域和蓝色区域都是最优区域。
     * 示例 2：
     *
     * 输入：points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]
     * 输出：3
     *
     *
     * 提示：
     *
     * n == points.length
     * 2 <= n <= 105
     * points[i].length == 2
     * 0 <= xi, yi <= 109
     * @param points
     * @return
     */
    public int maxWidthOfVerticalArea(int[][] points) {
        Arrays.sort(points, (o1,o2)->{return o1[0]-o2[0];});
        int max = 0;
        for(int i = 1; i < points.length; i++){
            max = Math.max(points[i][0] - points[i-1][0], max );
        }
        return max;
    }


    public static void main(String[] args){
        System.out.println(hammingWeight(-3));
        String a = "adds | d | fdsf | .dfdsf  dsfs ";
        System.out.println(Arrays.toString(a.split(" \\| ")));
    }
}
